package java学习.算法;

import java.util.Arrays;

import static 算法shiyan.shiayn3.归并排序.mergesort;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/3/10 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class mergeSort {

    public static void main(String[] args) {
        int[] arr = {6, 9, 7, 2, 1, 3, 5, 16, 4, 8, 36, 13, 44, 1};
        System.out.println("原数组" + Arrays.toString(arr));
        mergesort(arr, 0, arr.length - 1);
        System.out.println("现在："+Arrays.toString(arr));
    }

    private static void mergesort(int[] arr, int l, int r) {

        int m = l + ((r - l) >> 1);
//        int mid = left + ((right - left) >> 1);
        if (l < r) {
            mergesort(arr, m + 1, r);

            mergesort(arr, l, m );

            merge(arr, l, m, r);
        }

    }

    private static void merge(int[] arr, int l, int m, int r) {
        int[] temp = new int[(r - l) + 1];
        int x = 0;
        int i = l;
        int j = m + 1;
        while (i <= m && j <= r) {
            temp[x++] = arr[i] < arr[j] ? arr[i++] : arr[j++];
        }

        while (i<=m){
            temp[x++] = arr[i++];
        }
        while (j <= r){
            temp[x++] = arr[j++];
        }

        for (int k = l; k <=r ; k++) {
            arr[k] = temp[k-l];
        }
//        for (int n = 0; n <temp.length ; n++) {
//            arr[n+l] = temp[n];
//        }
    }
}